The problem can be found at the following link: Question Link
I have perform a Depth First Search (DFS) traversal of the tree.
- During the traversal, we'll maintain a map to keep track of whether a node at a certain level has been visited or not.
- Whenever we encounter a leaf node, we'll check if the distance between the current level and the leaf node is equal to K. If it is, and the node at the distance K from the leaf hasn't been visited before, we'll mark it as visited and increment the counter.
- We'll continue this process recursively for the left and right child nodes.
- Time Complexity: The time complexity of the algorithm is
O(N)
, whereN
is the number of nodes in the tree, since we visit each node once. - Auxiliary Space Complexity: The auxiliary space complexity is
O(N)
due to the usage of the unordered map to store nodes at each level.
class Solution {
public:
int cnt;
void dfs(Node* node, int& k, int lvl, unordered_map<int, bool>& mp) {
if (!node)
return;
mp[lvl] = false;
if (!node->left && !node->right) {
if (lvl - k >= 0 && !mp[lvl - k]) {
mp[lvl - k] = true;
cnt++;
}
}
++lvl;
dfs(node->left, k, lvl, mp);
dfs(node->right, k, lvl, mp);
}
int printKDistantfromLeaf(Node* root, int k) {
cnt = 0;
unordered_map<int, bool> mp;
dfs(root, k, 0, mp);
return cnt;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.